﻿// 0914train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>

using namespace std;


/*
输入描述
第一行输入为N，N代表坐标数量，N为正整数 N <= 100
之后的 N 行输入为坐标x y以空格分隔，x，y为整数，-10 <= x, y <= 10

输出描述
输出可以构成的正方形数量

输入
4
0 0
1 2
3 1
2 -1
输出
1

 */
class Solution01
{
public:
    string vec2str(vector<double>&pos_v)
    {
        stringstream pos_sstream;
        pos_sstream << pos_v[0] << ',' << pos_v[1];
        return pos_sstream.str();
	    //vec2str
    }

    vector<string>computePos(vector<double>&pos_1, vector<double>&pos_2)
    {
        //写公式
        //a+b=x_2-x_1 a-b=y_2-y_1
        //a=((x_2-x_1)+(y_2-y_1))/2
        //b=(x_2-x_1)-(y_2-y_1))/2
        //x_3=x_1+b y_3=y_1+a
        //x_4=x_1+a y_4=y_1-b
        double x_1 = pos_1[0], y_1 = pos_1[1];
        double x_2 = pos_2[0], y_2 = pos_2[1];

        double a = ((x_2 - x_1) + (y_2 - y_1)) / 2;
        double b = ((x_2 - x_1) - (y_2 - y_1)) / 2;

        double x_3 = x_1 + b, y_3 = y_1 + a;
        double x_4 = x_1 + a, y_4 = y_1 - b;

        vector<string>result;
        vector<double>pos_3 = { x_3, y_3 };
        string str_pos_3 = vec2str(pos_3);
        result.push_back(str_pos_3);

        vector<double>pos_4 = {x_4, y_4};
        string str_pos_4 = vec2str(pos_4);
        result.push_back(str_pos_4);

        return result;
        //computePos
    }

    Solution01(vector<vector<double>>&point_vec)
    {
        if (point_vec.size()<4)
        {
            cout << 0;
            return;
        }

        unordered_map<string, vector<string>>point_map;

        for (int i=0; i<point_vec.size(); i++)
        {
            for (int next=i+1; next <point_vec.size(); next++)
            {
                vector<string>other_point = computePos(point_vec[i], point_vec[next]);

            	string i_str = vec2str(point_vec[i]);
                string next_str = vec2str(point_vec[next]);
                string key = i_str + ' ' + next_str;
                point_map[key] = other_point;

                //for next
            }
            string i_str = vec2str(point_vec[i]);
            total_point.insert(i_str);
            //for i
        }

        //扫一遍point_map，set中是否有对应的点
        int result = 0;
        for (auto& map_item : point_map)
        {
            bool is_find = true;
            for (auto& p_item : map_item.second)
            {
	            if (total_point.count(p_item)==0)
	            {
                    is_find = false;
	            }
            }
            //对角点全部找齐
            if (is_find)
            {
                result += 1;
            }
        }
        //两个对角会重复计算，正方形数量=对角线/2
        cout << result/2;
        //Solution01
    }
private:
    unordered_set<string>total_point;//全局所有点的坐标
};


/*
 每个数字对应多个字母，对应关系如下：
0：a,b,c
1：d,e,f
2：g,h,i
3：j,k,l
4：m,n,o
5：p,q,r
6：s,t
7：u,v
8：w,x
9：y,z
输入一串数字后，通过数字和字母的对应关系可以得到多个字母字符串（要求按照数字的顺序组合字母字符串）;
屏蔽字符： 屏蔽字符中的所有字母不能同时在输出的字符串出现，
如屏蔽字符时 abc，则要求字符串中不能同时出现 a，b，c，但是允许同时出现 a，b；a，c；b，c 等。

给定一个数字字符串和一个屏蔽字符串，输出所有可能的字符组合；
例如输入数字字符串 78 和屏蔽字符串 ux，输出结果为 uw，vw，vx；数字字符串 78，可以得到如下字符串： uw，ux，vw，vx；由于 ux 是屏蔽字符串，因此排除 ux，最终的输出时 uw，vw，vx；

输入描述
第一行输入为一串数字字符串，数字字符串中的数字不允许重复，数字字符串的长度大于 0，小于等于 5；
第二行输入是屏蔽字符，屏蔽字符的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复。

输出描述
输出可能的字符串组合
注：字符串之间使用逗号隔开，最后一个字符串后携带逗号

输入
78
ux

输出
uw,vw,vx,
*/
class Solution02
{
public:
    void initData(string& exclu)
    {
/*
0：a,b,c
1：d,e,f
2：g,h,i
3：j,k,l
4：m,n,o
5：p,q,r
6：s,t
7：u,v
8：w,x
9：y,z
*/
        vector<string>combine_vec = {
		"a,b,c","d,e,f","g,h,i","j,k,l","m,n,o",
		"p,q,r","s,t","u,v","w,x","y,z"
        };

        for (int i=0; i<combine_vec.size(); i++)
        {
            string str_item = combine_vec[i];
            vector<char>char_vec;
            stringstream combine_sstream(str_item);
            string token;
            while (getline(combine_sstream, token, ','))
            {
                char_vec.push_back(token[0]);
            }
            combine_map[i] = char_vec;
        }

        for (auto&ch:exclu)
        {
            exclu_vec.push_back(ch);
        }
        //initData
    }
    void backTrack(string& num_str, int index)
    {
        if (track_vec.size()==num_str.size())
        {
            bool is_verify = false;
            //遍历exclu，只要有一个不在track_set里，符合要求
            //屏蔽字符中的所有字母，不能同时，出现
            for (auto&exclu_ch:exclu_vec)
            {
                if (track_set.count(exclu_ch) == 0)
                    is_verify = true;
            }

            if (is_verify)
            {
                string res;
                for (auto& ch : track_vec)
                {
                    res += ch;
                }
                result.push_back(res);
            }
            return;
        }
        
        if (index==num_str.size())
        {
            return;
        }

        int level = num_str[index] - '0';
        vector<char>curr_vec = combine_map[level];

        for (auto&curr_ch:curr_vec)
        {
            //做选择
            track_vec.push_back(curr_ch);
            track_set.insert(curr_ch);
            //回溯
            backTrack(num_str, index + 1);
            //撤销选择
            track_vec.pop_back();
            track_set.erase(curr_ch);
        }

        //backTrack
    }
    Solution02(string&num_str, string&exclu)
    {
        initData(exclu);

        backTrack(num_str, 0);

        for (auto&str:result)
        {
            cout << str << ',';
        }
        //Solution02
    }
private:
    vector<char>track_vec;
    vector<string>result;
    unordered_set<char>track_set;
    vector<char>exclu_vec; //屏蔽字符
    unordered_map<int, vector<char>>combine_map;
};


/*
 现有一个CPU和一些任务需要处理，已提前获知每个任务的任务ID、优先级、所需执行时间和到达时间
CPU同时只能运行一个任务，请编写一个任务调度程序，采用“可抢占优先权调度”调度算法进行任务调度，规则如下：

1 如果一个任务到来时，CPU是空闲的，则CPU可以运行该任务直到任务执行完毕
但是如果运行中有一个更高优先级的任务到来，则CPU必须暂停当前任务去运行这个优先级更高的任务；

2 如果一个任务到来时，CPU正在运行一个比他优先级更高的任务时，新到达的任务必须等待；

3 当CPU空闲时，如果还有任务在等待，CPU会从这些任务中选择一个优先级最高的任务执行，
相同优先级的任务选择到达时间最早的任务

输入描述
输入有若干行，每一行有四个数字（均小于10^8），分别为任务ID，任务优先级，执行时间和到达时间。每个任务的任务ID不同，优先级数字越大优先级越高，并且相同优先级的任务不会同时到达
输入的任务已按照到达时间从小到大排序，并且保证在任何时间，处于等待的任务不超过10000个

输出描述
按照任务执行结束的顺序，输出每个任务的任务ID和对应的结束时间。
示例一
输入
1 3 5 1
2 1 5 10
3 2 7 12
4 3 2 20
5 4 9 21
6 4 2 22
输出
1 6
3 19
5 30
6 32
4 33
2 35


任务ID、优先级、所需执行时间和到达时间
1 3 5 1 优先级3 所需执行时间5 到达时间1
 */
class Solution03
{
public:
    struct Task
    {
        //任务ID 优先级 所需执行时间 到达时间
        int id, priority, duration, arrive;
        Task() = default;
        Task(int id, int priority, int duration, int arrive) :id(id),
            priority(priority), duration(duration), arrive(arrive) {};

        bool operator < (const Task&other) const
        {
            //相同优先级, 到达时间最早
            if (priority==other.priority)
            {
                return arrive > other.arrive;
            }
            return priority < other.priority;
        }
    };

    Solution03(vector<vector<int>>&origin_vec)
    {
        //按到达时间排序
        sort(origin_vec.begin(), origin_vec.end(), [](vector<int>&vec_1,vector<int>&vec_2)
            {
            //任务ID 优先级 所需执行时间 到达时间3
                return vec_1[3] < vec_2[3];

            });

        vector<Task>task_list(origin_vec.size());
        for (int i = 0; i < origin_vec.size(); i++)
        {
            vector<int>curr_vec = origin_vec[i];
            Task curr_t(curr_vec[0], curr_vec[1], curr_vec[2], curr_vec[3]);
            task_list[i] = curr_t;
        }

        priority_queue<Task>exec_queue;
        int index = 0; //待推进任务index
        int curr_time = 0;

        int list_size = task_list.size();
        while (index < task_list.size() || !exec_queue.empty())
        {
            if (exec_queue.empty())
            {
                exec_queue.push(task_list[index]);
                //当前时间，任务到达时间
                curr_time = task_list[index].arrive;
                index++;
            }


            if (!exec_queue.empty())
            {
                //取出队头任务
                Task top_task = exec_queue.top();
                exec_queue.pop();

                //计算是否被抢占
                int top_complete = curr_time + top_task.duration;
                bool is_occupy = false;
                //index 待入队任务
                if (index < list_size)
                {
                    if (task_list[index].arrive < top_complete)
                        is_occupy = true;
                }
                if (is_occupy)
                {
                    int constrain = task_list[index].arrive - curr_time;
                    top_task.duration -= constrain;
                    exec_queue.push(top_task);

                    //推进新的任务
                    exec_queue.push(task_list[index]);
                    //更新curr_time
                    curr_time = task_list[index].arrive;
                    index++;
                    continue;
                }
                //如果没有被抢占，直接执行完成
                //更新curr_time
                curr_time = top_complete;
                vector<int>task_res = { top_task.id, top_complete };
                result.push_back(task_res);
            }

            //while
        }

        for (auto&res_vec:result)
        {
            cout << res_vec[0] << ' ' << res_vec[1] << endl;
        }

        //Solution03
    }
private:
    vector<vector<int>>result;
};



int main()
{
	{
        vector<vector<int>>origin_vec;
        string input;
        while (getline(cin, input))
        {
            if (input.empty()) break;
            stringstream oh_sstream(input);
            string token;

            vector<int>item_vec;
            while (oh_sstream>>token)
            {
                item_vec.push_back(stoi(token));
            }
            origin_vec.push_back(item_vec);
        }

        Solution03 solu(origin_vec);

        return 0;
	}
	{
/*
78
ux
*/
        string num_str, exclu_str;
        cin >> num_str >> exclu_str;

        Solution02 solu(num_str, exclu_str);

        return 0;
	}
/*
4
0 0
1 2
3 1
2 -1
*/
    int v_size;
    cin >> v_size;
    vector<vector<double>>point_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        vector<double>single_point(2);
        cin >> single_point[0] >> single_point[1];
        point_vec[i] = single_point;
    }

    Solution01 solu(point_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
